package com.singzi.leetcode.jianzhiOffer2;

import java.util.*;

public class T0030 {
}
class RandomizedSet {

    Random random = new Random();
    List<Integer> list;
    HashMap<Integer, Integer> map;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        int index = list.size();
        list.add(val);
        map.put(val, index);
        return true;

    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }else {
            int index = map.get(val);
            int last = list.get(list.size()-1);
            list.set(index, last);
            list.remove(list.size()-1);
            map.put(last, index);
            map.remove(val);
            return true;
        }
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int index  = random.nextInt(list.size());
        return list.get(index);
    }
}